/**************************************************************
*
* M3D_POLY.H
*
* Polygons & Planes operations
**************************************************************/

//
// Global defines
//
#define M3D_CODE_LEFT     0x01 // These are the constants for m3dClipLSegRect()
#define M3D_CODE_ABOVE    0x02 // Also used by ClipRect()
#define M3D_CODE_RIGHT    0x04
#define M3D_CODE_BELOW    0x08
#define M3D_CODE_ABOVE_Z  0x10 
#define M3D_CODE_BELOW_Z  0x20


//
// Triangles classes
//

struct m2dTRI {
   m2dV   v1, v2, v3;   // triangle's points
   m2dV&   operator[]  (int i)  { STRONG_ASSERT(i >= 0 && i < 3); return ((m2dV*)&v1)[i]; }
   m2dV*   GetVert     (int i)  { STRONG_ASSERT(i >= 0 && i < 3); return &((m2dV*)&v1)[i]; }
   m2dV*   GetVertList (void)   { return &v1;              }
   m2dTRI& operator =  (const class m2dPOLY &poly);
};

struct m3dTRI {
   m3dV   v1, v2, v3;  // triangle's points
   m3dV&   operator[]  (int i)  { return ((m3dV*)&v1)[i]; }
   const m3dV&   operator[]  (int i) const { return ((m3dV*)&v1)[i]; }
   m3dV*   GetVert     (int i) {return &((m3dV*)&v1)[i]; }
   const m3dV*   GetVert     (int i) const {return &((m3dV*)&v1)[i]; }
   m3dV*   GetVertList (void)   {return &v1;              }
   m3dTRI& operator=   (const class m3dPOLY &poly);
};



//
// Polygon classes
//
class m3dPOLY {
public:
   int    nVert;
   m3dV   vert[M3D_MAX_NVERT];
   
   m3dV&    operator[] (int i)         {return vert[i];}
   float    GetSquare  (void);

   // faster than direct assignment, since fewer points are copied
   m3dPOLY& operator = (const m3dPOLY &poly) { nVert = poly.nVert; memcpy(vert, poly.vert, sizeof(m3dV)*nVert);  return *this;}
   m3dPOLY& operator = (const m3dTRI  &tri)  { nVert = 3; vert[0] = tri.v1; vert[1] = tri.v2; vert[2] = tri.v3; return *this;}
};

class m2dPOLY {
public:
   int    nVert;
   m2dV   vert[M3D_MAX_NVERT];

   m2dV&    operator[](int i)            {return vert[i];}
   const m2dV&    operator[](int i) const {return vert[i];}
   // faster than direct assignment, since fewer points are copied
   m2dPOLY& operator= (const m2dPOLY &poly) {nVert = poly.nVert; memcpy(vert, poly.vert, sizeof(m2dV)*nVert); return *this;}
   m2dPOLY& operator= (const m2dTRI  &tri)  { nVert = 3; vert[0] = tri.v1; vert[1] = tri.v2; vert[2] = tri.v3; return *this;}
};

__INLINE m2dTRI& m2dTRI::operator= (const class m2dPOLY &poly) 
{ 
   ASSERT(poly.nVert == 3); 
   v1 = poly.vert[0]; v2 = poly.vert[1];  v3 = poly.vert[2]; 
   return *this;
}
__INLINE m3dTRI& m3dTRI::operator= (const class m3dPOLY &poly) 
{ 
   ASSERT(poly.nVert == 3); 
   v1 = poly.vert[0]; v2 = poly.vert[1];  v3 = poly.vert[2]; 
   return *this;
}


// access to fields of polygons
#define m3dPolyNVert(poly)      ((poly)->nVert)
#define m3dPolyVertList(poly)   ((poly)->vert)
#define m3dPolyVertex(poly,n)   ((poly)->vert + (n))
#define m3dPolyVertexX(poly,n)  (((poly)->vert + (n))->x)
#define m3dPolyVertexY(poly,n)  (((poly)->vert + (n))->y)
#define m3dPolyVertexZ(poly,n)  (((poly)->vert + (n))->z)

extern void m3dGetPolyEdge      (const m3dPOLY *poly, int indEdge, m3dV *lB, m3dV *lE);

//
// Compare polygons
//
extern BOOL m3dIsEqualPoly_A (m3dPOLY *poly1, m3dPOLY *poly2, float acc );
extern BOOL m2dIsEqualPoly_A (m2dPOLY *poly1, m2dPOLY *poly2, float acc );

#define m3dIsEqualPoly(poly1,poly2) m3dIsEqualPoly_A(poly1,poly2,M3D_EPSILON) 
#define m2dIsEqualPoly(poly1,poly2) m2dIsEqualPoly_A(poly1,poly2,M3D_EPSILON) 

extern float m3dCalcTriArea2      (m3dV *v1, m3dV *v2, m3dV *v3);
extern float m2dCalcTriArea2      (m2dV *v1, m2dV *v2, m2dV *v3);

#define m3dCalcTriArea(v1, v2, v3) (m3dSqrt(m3dCalcTriArea2(v1, v2, v3)))
#define m2dCalcTriArea(v1, v2, v3) (m3dSqrt(m2dCalcTriArea2(v1, v2, v3)))

extern float m3dCalcPolyArea      (m3dPOLY *poly);
extern float m2dCalcPolyArea      (m2dPOLY *poly);

// convert polygon representations
extern void m3xyPoly3DToPoly2D (m3dPOLY *poly3D, m2dPOLY *poly2D);
extern void m3xzPoly3DToPoly2D (m3dPOLY *poly3D, m2dPOLY *poly2D);
extern void m3yzPoly3DToPoly2D (m3dPOLY *poly3D, m2dPOLY *poly2D);

extern void m3xyPoly2DToPoly3D (m2dPOLY *poly2D, m3dPOLY *poly3D);
extern void m3xzPoly2DToPoly3D (m2dPOLY *poly2D, m3dPOLY *poly3D);
extern void m3yzPoly2DToPoly3D (m2dPOLY *poly2D, m3dPOLY *poly3D);

//
// re-orient polygon vertices (if needed) to create a CCW polygon
//
extern void m3dReOrientPoly   (m3dPOLY *poly);
extern void m2dReOrientPoly   (m2dPOLY *poly);
extern BOOL m2dOrientCCWPoly  (m2dPOLY *poly);

extern void m2dTriGetBasisCoord    (m2dTRI  *poly, m2dV *coord, float *kA, float *kB);
extern void m2dTriApplyBasisCoord  (m2dTRI  *poly, float kA, float kB, m2dV *coord);
extern void m2dPolyGetBasisCoord   (m2dPOLY *poly, m2dV *coord, float *kA, float *kB);
extern void m2dPolyApplyBasisCoord (m2dPOLY *poly, float kA, float kB, m2dV *coord);

extern void m3dTriGetBasisCoord    (m3dTRI  *poly, m3dV *coord, float *kA, float *kB);
extern void m3dTriApplyBasisCoord  (m3dTRI  *poly, float kA, float kB, m3dV *coord);
extern void m3dPolyGetBasisCoord   (m3dPOLY *poly, m3dV *coord, float *kA, float *kB);
extern void m3dPolyApplyBasisCoord (m3dPOLY *poly, float kA, float kB, m3dV *coord);

// poly/plane normal/perVector calculation
extern void         m3dGetTriNormal      (m3dTRI  *tri,  m3dV *norm);
extern BOOL        _m3dGetTriNormal      (m3dTRI  *tri,  m3dV *norm);
extern void         m3dGetPolyNormal     (m3dPOLY *poly, m3dV *norm);
extern BOOL        _m3dGetPolyNormal     (m3dPOLY *poly, m3dV *norm);
extern void         m3dGetPlaneNormal    (m3dV *pV1, m3dV *pV2, m3dV *pV3, m3dV *norm);
extern void __CDECL m3dGetPolyPerpVector (m3dPOLY *poly, m3dV *norm);
extern void __CDECL m3dGetPlanePerpVector(m3dV *pV1, m3dV *pV2, m3dV *pV3, m3dV *norm);

extern void  m2dCalcPolyMassCenter(m2dPOLY *pPoly, m2dV *center);
extern void  m3dCalcPolyMassCenter(m3dPOLY *pPoly, m3dV *center);
extern float m2dCalcPolyPerimeter (m2dPOLY *pPoly);
extern float m3dCalcPolyPerimeter (m3dPOLY *pPoly);


//
// Diameter of polygon (max distance between polygon points)
//
extern float m2dGetPolyDiameter(m2dPOLY *poly2D, m2dV *lB, m2dV *lE);

//
// Drop repeat vertices in polygons
//
extern BOOL m2dDropPolyRepeatVertices (m2dPOLY *poly2D);
extern BOOL m3dDropPolyRepeatVertices (m3dPOLY *poly3D);


extern BOOL m2dIsPolyConvexCCW(const m2dPOLY *poly);
extern BOOL m2dIsPolyCCW      (m2dPOLY *poly);
extern BOOL m2dIsPolySelfCross(m2dPOLY *poly);

extern void m2dGetPolyBBox (m2dPOLY *poly, m2dV *bll, m2dV *fur);
extern void m3dGetPolyBBox (m3dPOLY *poly, m3dV *bll, m3dV *fur);


//
// Polygons intersections & qualifications
//
//
// Polygon convex hull calculation/check if point belongs to poly/polygon intersection
//
#define m2dIsBelongPointTri(tri,v)             m2dIsBelongPointTri_A  (tri, v,M3D_EPSILON)
#define m2dIsBelongPointPoly(poly,v)           m2dIsBelongPointPoly_A (poly,v,M3D_EPSILON)
#define m3xzIsBelongPointPoly(poly,v)          m3xzIsBelongPointPoly_A(poly,v,M3D_EPSILON)
#define m3xyIsBelongPointPoly(poly,v)          m3xyIsBelongPointPoly_A(poly,v,M3D_EPSILON)
#define m3yzIsBelongPointPoly(poly,v)          m3yzIsBelongPointPoly_A(poly,v,M3D_EPSILON)
#define m3dIsBelongPointPoly(poly,v,n)         m3dIsBelongPointPoly_A(poly,v,n,M3D_EPSILON)
#define m2dIsCrossLSegPolyBoundary(poly,v1,v2) m2dIsCrossLSegPolyBoundary_A(poly,v1,v2,M3D_EPSILON)

extern BOOL m2dIsBelongPointTri_A        (m2dTRI  *tri,  m2dV *v, float accuracy);
extern BOOL m2dIsBelongPointPoly_A       (m2dPOLY *poly, m2dV *v, float accuracy);
extern BOOL m2dIsBelongPointPoly_S       (m2dPOLY *poly, m2dV *v, float accuracy);
extern BOOL m2dIsCrossLSegPolyBoundary_A (m2dPOLY *poly, m2dV *v1, m2dV *v2, float accuracy);
extern BOOL m3xzIsBelongPointPoly_A      (m3dPOLY *poly3D, m3dV *v, float accuracy);
extern BOOL m3xyIsBelongPointPoly_A      (m3dPOLY *poly3D, m3dV *v, float accuracy);
extern BOOL m3yzIsBelongPointPoly_A      (m3dPOLY *poly3D, m3dV *v, float accuracy);
extern BOOL m3dIsBelongPointPoly_A       (m3dPOLY *poly, m3dV *v, m3dV *norm, float accuracy);

//
// line segments/polygons clipping
//
extern int  m2dClipPolyLSeg (m2dPOLY *poly, m2dV *lB, m2dV *lE, m2dPOLY *polyClip);
extern int  m2dClipPolyPoly (m2dPOLY *poly, m2dPOLY *polyClipBy, m2dPOLY *polyClip );
extern int  m2dClipPolyRect   (m2dPOLY *poly, m2dPOLY *polyRect, m2dPOLY *polyClip );
extern int  m2dClipTriRect    (m2dTRI  *tri,  m2dPOLY *polyRect, m2dPOLY *polyClip );
extern int  m2dClipLSegRect   (m2dV *lB, m2dV *lE, m2dPOLY *polyClip, m2dV *lBClip, m2dV *lEClip);
extern int  m3xyClipLSegRect  (m3dV *lB, m3dV *lE, m2dPOLY *polyClip, m3dV *lBClip, m3dV *lEClip);

//
// clipping by planes arbitrary/near/far
//
extern int  m3dClipPolyPlane     (const m3dPOLY *poly, const m3dV *point, const m3dV *norm, m3dPOLY* polyClip);
extern int  m3dClipPolyNearPlane (m3dPOLY *poly, float dist, m3dPOLY *polyClip);
extern int  m3dClipPolyFarPlane  (m3dPOLY *poly, float dist, m3dPOLY *polyClip);
extern int  m3dClipLSegNearFar   (m3dV *lB, m3dV *lE, float nearPl, float farPl);

//
// Ray <->polygon/plane intersection
//
extern BOOL  m3dIsectRayVNPlane  (const m3dV *rayOrg, const m3dV *rayDir, const m3dV *point, const m3dV *norm, m3dV *v, float *dist = NULL);
extern BOOL  m3dIsectRayPlane    (m3dV *rayOrg, m3dV *rayDir, m3dPOLY *poly, m3dV *v, m3dV *norm = NULL, float *dist = NULL);
extern BOOL _m3dIsectRayVNPlane  (m3dV *rayOrg, m3dV *rayDir, m3dV *point, m3dV *norm, m3dV *v, float *dist = NULL);
extern BOOL  m3dIsectRayTri      (m3dV *rayOrg, m3dV *rayDir, m3dV *v0, m3dV *v1, m3dV *v2, float *dist);
extern BOOL _m3dIsectRayTri      (m3dV *rayOrg, m3dV *rayDir, m3dV *v0, m3dV *v1, m3dV *v2, float *dist, BOOL *isBF);
extern BOOL  m3dIsectRayDomPoly  (m3dV *rayOrg, m3dV *rayDir, m2dPOLY *poly, float yLo, float yHi, float *dist);

//
// line <-> polygon/plane intersection
// '_' is used because line is specified as ray
//
extern BOOL _m3dIsectRayPlane     (m3dV *rayOrg, m3dV *rayDir, m3dPOLY *poly, m3dV *v );
extern BOOL _m3dIsectRayPlane_N   (m3dV *rayOrg, m3dV *rayDir, m3dPOLY *poly, m3dV *v, m3dV *norm );
extern BOOL _m3dIsectRayPlane_NT  (m3dV *rayOrg, m3dV *rayDir, m3dPOLY *poly, m3dV *v, m3dV *norm, float *dist );
extern BOOL _m3dIsectRayVNPlane_T (m3dV *rayOrg, m3dV *rayDir, m3dV *point, m3dV *norm, m3dV *v, float *dist);

extern BOOL  m3dIsectPlanePlane   (m3dV *v1, m3dV *n1, m3dV *v2, m3dV *n2, m3dV *vOrg, m3dV *vDir);
extern BOOL  m3dIsectLSegPoly     (m3dV *vB, m3dV *vE, m3dPOLY *poly, m3dV *vNorm, m3dV *vIsect);
extern BOOL  m3dIsectLSegPlane    (m3dV *vB, m3dV *vE, m3dV *vert, m3dV *norm, m3dV *vIsect);

extern BOOL  m3dIsectRayTri       (m3dV *rayOrg, m3dV *rayDir, m3dV *v0, m3dV *v1, m3dV *v2, float *dist);
extern BOOL _m3dIsectRayTri       (m3dV *rayOrg, m3dV *rayDir, m3dV *v0, m3dV *v1, m3dV *v2, float *dist, BOOL *isBF);

extern float m2dDistPointTri      (m2dV *point, m2dTRI  *tri,  m2dV *vClosest);
extern float m2dDistPointPoly     (m2dV *point, m2dPOLY *poly, m2dV *vClosest);
extern BOOL  m3dDistPointPoly     (const m3dV *point, m3dPOLY *poly, m3dV *norm, BOOL isIncludeBF, m3dV *vClosest, float *dist, float distAlpha);
extern BOOL  m3dDistPointTri_2    (const m3dV *point, const m3dV *v0, const m3dV *v1, const m3dV *v2, BOOL isCullBF, float distAlphaCut_2, float *dist_2, m3dV *vClosest);
extern BOOL  m3dDistPointTri      (const m3dV *point, const m3dV *v0, const m3dV *v1, const m3dV *v2, BOOL isCullBF, float distAlphaCut,   float *dist,   m3dV *vClosest);

extern float m3dDistPointPlane    (const m3dV *pV3D, m3dPOLY *poly3D, m3dV *norm = NULL);
extern float m3dDistPointPlane_S  (m3dV *pV3D, m3dPOLY *poly3D, m3dV *norm = NULL);
extern BOOL  m3dDistLSegPoly      (m3dV *lB, m3dV *lE, m3dPOLY *poly, m3dV *norm, 
                                   m3dV *vClosLSeg, m3dV *vClosPoly, float *minDist, int *indEdge, float distAlpha);
extern BOOL  m3dDistLSegPlane     (m3dV *lB, m3dV *lE, m3dV *vert, m3dV *norm, 
                                   m3dV *vClosLSeg, m3dV *vClosPlane, float *minDist, float distAlpha);

extern int   m3dQualVListPlane    (m3dV *planePoint, m3dV *planeNormal, int nVert, m3dV *vList);

/*************************************************************
* m3dDistPointPlane()
* m3dDistPointPlane_S()
*
* IN:  pV3D - point in 3D
*      vert - point from the plane
*      norm - normal to the plane
* RET: distance from point to the plane
*
* Calculate the distance between plane (specified by a vertex and normal)
* and a given point in space
* dist = FAbs(norm*pV3D - norm*Vert0) = FAbs(norm*(pV3D - Vert0))
*************************************************************/
__INLINE float m3dDistPointPlane (const m3dV *point, const m3dV *vert, const m3dV *norm)
{
   m3dV   v;

   m3dCheckValid(point);
   m3dCheckValid(vert);
   m3dCheckValid(norm);

   m3dSubtractVector(point, vert, &v);
   return m3dFAbs(m3dDotProduct(&v, norm));
}

__INLINE float m3dDistPointPlane_S (const m3dV *point, const m3dV *vert, const m3dV *norm)
{
   m3dV   v;

   m3dCheckValid(point);
   m3dCheckValid(vert);
   m3dCheckValid(norm);

   m3dSubtractVector(point, vert, &v);
   return m3dDotProduct(&v, norm);
}

/***************************************************************************
*  m3dProjPointPlane ( )
*     Project point onto plane
* IN:  vert  - point from the plane
*      norm  - normal to the plane
*      point - point to project
* OUT: v - projected point
* RET: dist point plane
***************************************************************************/
__INLINE float m3dProjPointPlane (const m3dV *vert, const m3dV *norm, const m3dV *point, m3dV *v)
{
   m3dV     dir;
   float    dist;

   dist = m3dDistPointPlane_S(point, vert, norm);

   // move point along plane normal
   m3dScaleVector(norm, -dist, &dir);
   m3dAddVector(point, &dir, v);

   ASSERT(m3dDistPointPlane(v, vert, norm) < 100.f*M3D_EPSILON);
   return dist;
}

/***************************************************************************
*  _m3dProjPointPlane ( )
*     Project point onto plane
* IN:  vert  - point from the plane
*      norm  - normal to the plane
*      point - point to project
* OUT: point - projected point
* RET: dist point plane
***************************************************************************/
__INLINE float _m3dProjPointPlane (m3dV *vert, m3dV *norm, m3dV *point)
{
   m3dV     dir;
   float    dist;

   dist = m3dDistPointPlane_S(point, vert, norm);

   // move point along plane normal
   m3dScaleVector(norm, -dist, &dir);
   _m3dAddVector(point, &dir);

   return dist;
}


//
// intersect polygon and circle in XZ
//
extern BOOL m3xzIsIsectPolyCircle (m3dPOLY *poly, m3dV *org, float radius);

//
// End of file 'M3D_POLY.H'
//
